EVENTO
CRIPTOGRAFIA POST-QUÂNTICA
Tipo de evento: Exame de Qualificação
NAS ULTIMAS TRÊS DÉCADAS, OS ESQUEMAS CRIPTOGRÁFICOS DE CHAVE PÚBLICA TÊM MUDADO COMPLETAMENTE O PANORAMA DOS NOSSOS SISTEMAS DE COMUNICAÇÃO MODERNOS. ATUALMENTE SÃO CONSIDERADOS INDISPENSÁVEIS NAS BASES DOS SISTEMAS DE COMUNICAÇÃO. A SEGURANÇA DOS ESQUEMAS CRIPTOGRÁFICOS USADOS ATUALMENTE COMO RSA, DSA, ECDSA E SIMILARES DEPENDEM PRESSUPOSTOS COM RELAÇÃO À DIFICULDADE DE CERTOS PROBLEMAS NA TEORIA DOS NÚMEROS, COMO O PROBLEMA DA FATORAÇÃO DE INTEIROS OU O PROBLEMA DO LOGARITMO DISCRETO.PORÉM, EM 1994 PETER SHOR, DOS LABORATÓRIOS DE BELL, MOSTROU QUE OS COMPUTADORES QUÂNTICOS PODEM QUEBRAR QUALQUER ESQUEMA CRIPTOGRÁFICO DE CHAVE PÚBLICA QUE ESTEJA BASEADO NESTES PROBLEMAS DA TEORIA DOS NÚMEROS. ISTO SIGNIFICA QUE, SE FOSSE CONSTRUÍDO UM COMPUTADOR QUÂNTICO, A SEGURANÇA DE TODA A COMUNICAÇÃO MODERNA DESDE A CIFRAÇÃO ATÉ A ASSINATURA DIGITAL FICARÁ VULNERÁVEL. EM 2001, ISSAC CHUANG DA IBM IMPLEMENTOU O ALGORITMO DE SHOR NUM COMPUTADOR QUÂNTICO DE 7 QUBITS. OS FÍSICOS PREDIZEM QUE NOS 20 ANOS SEGUINTES APROXIMADAMENTE EXISTIRÃO COMPUTADORES QUÂNTICOS QUE SERÃO SUFICIENTEMENTE GRANDES COMO PARA IMPLEMENTAR AS IDEIAS DE SHOR E ASSIM QUEBRAR BASICAMENTE TODOS OS ESQUEMAS DE CHAVE PÚBLICAS USADAS ATUALMENTE. PERCEBEMOS ENTÃO QUE PRECISAMOS PREVER UM POSSÍVEL FUTURO COM COMPUTADORES QUÂNTICOS, E DEVEMOS COMEÇAR A PREPARAR O MUNDO CRIPTOGRÁFICO PARA ESSE FUTURO.NESTE CONTEXTO, EXISTEM MUITOS ESFORÇOS NA PROCURA DE ESQUEMAS CRIPTOGRÁFICOS DE CHAVE PÚBLICA ALTERNATIVOS RESISTENTES AOS ATAQUES DE COMPUTADORES QUÂNTICOS E ESTA NOVA ÁREA DENOMINA-SE CRIPTOGRAFIA PÓS-QUÂNTICA. ESSE ESFORÇOS TÊM CRIADO PRINCIPALMENTE QUATRO CLASSES DE ESQUEMAS CRIPTOGRÁFICOS, A SABER, OS ESQUEMAS BASEADOS EM FUNÇÕES HASH, OS BASEADOS EM CÓDIGOS, OS BASEADOS EM MULTIVARIADOS QUADRÁTICOS E OS BASEADOS EM RETICULADOS .NESTE TRABALHO, AINDA EM ANDAMENTO, NOS FOCAREMOS NAS TRÊS PRIMEIRAS CLASSES CITADAS ACIMA. NA PRIMEIRA PARTE UMA DAS NOSSAS PERSPECTIVAS É PROPOR UMA MODIFICAÇÃO DO ESQUEMA MERKLE, DESCRITO NA REF. [1], USANDO CÓDIGOS LINEARES COM O OBJETIVO PRINCIPAL DE ASSINAR MAIS DOCUMENTOS SEM PRECISAR AUMENTAR O TAMANHO DA ÁRVORE DE MERKLE. PARA GARANTIR QUE A MODIFICAÇÃO SEJA RESISTENTE AOS ATAQUES QUÂNTICOS, USAMOS O FATO DO PROBLEMA COMPUTACIONAL DA DECODIFICAÇÃO DE UM CÓDIGO LINEAR BINÁRIO SER NP-COMPLETO [2]. NA SEGUNDA PARTE TRABALHAREMOS COM ATAQUES DO TIPO ALGÉBRICO E DE MIN-RANK, CITADOS NAS REFERÊNCIAS [3] E [4] RESPECTIVAMENTE, CONTRA SISTEMAS BASEADOS EM MULTIVARIÁVEIS QUADRÁTICAS. BIBLIOGRAFIA:[1] R. MERKLE, A CERTIFIED DIGITAL SIGNATURE, IN ADVANCES IN CRYPTOLOGY CRYPTO 89 PROCEEDINGS, SER. LECTURE NOTES IN COMPUTER SCIENCE, G. BRASSARD, ED. SPRINGER NEW YORK, 1990, VOL. 435, PP. 218238. AVAILABLE: HTTP://DX.DOI.ORG/10.1007/0-387-34805-0_21.[2] E. R. BERLEKAMP, R. J. MCELIECE, AND H. C. A. VAN TILBORG, ON THE INHERENT INTRACTABILITY OF CERTAIN CODING PROBLEMS (CORRESP.), IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 24, NO. 3, PP. 384386, 1978.[3] PATARIN, J. (1995). CRYPTANALYSIS OF THE MATSUMOTO AND IMAI PUBLIC KEY SCHEME OF EUROCRYPT88. IN COPPERSMITH, D., EDITOR, ADVANCES IN CRYPTOLOGY CRYPT095, VOLUME 963 OF LECTURE NOTES IN COMPUTER S CIENCE, PAGES 248261. SPRINGERBERLIN HEIDELBERG.[4] J.O. SHALLIT, G.S. FRANDSEN, AND J.F. BUSS. THE COMPUTATIONAL COMPLEXITY OF SOME PROBLEMS OF LINEAR ALGEBRA. BRICS SERIES REPORT, AARHUS, DENMARK, RS-96-33. (ALSO AT HTTP://WWW.BRICS.DK/RS/96/33).
Data Início: 27/11/2014 Hora: 14:00 Data Fim: 27/11/2014 Hora: 17:00
Local: LNCC - Laboratório Nacional de Computação Ciêntifica - Auditorio A
Aluno: Juan Del Carmen Grados Vázquez - Laboratório Nacional de computação Científica - LNCC
Orientador: Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Participante Banca Examinadora: Antônio Tadeu Azevedo Gomes - Laboratório Nacional de Computação Científica - LNCC Artur Ziviani - Laboratório Nacional de Computação Científica - LNCC Jauvane Cavalcante de Oliveira - Laboratório Nacional de Computação Científica - LNCC
